//
// Created by shanshi on 2025/6/9.
//

#ifndef LRU_H
#define LRU_H

# include <iostream>
# include <unordered_map>
# include <memory>
# include <mutex>
# include <cstddef>

template<typename Key, typename Value>
class KICachePolicy;
template<typename Key, typename Value>
class KLruCache;

template<typename Key, typename Value>
class LruNode {
    private:
        Key key_;
        Value value_;
        size_t access_count_; // 访问次数
        std::weak_ptr<LruNode<Key, Value>> prev_; // 前一个节点
        std::shared_ptr<LruNode<Key, Value>> next_; // 后一个节点
    public:
        LruNode(Key k, Value v) : key_(k), value_(v), access_count_(0), prev_(nullptr), next_(nullptr) {}
        // 获取key
        Key key() const { return key_; }
        // 获取value
        Value value() const { return value_; }
        // 获取访问次数
        size_t access_count() const { return access_count_; }
        // set value
        void set_value(const Value& v) { value_ = v; }
        // 增加访问次数
        void increase_access_count() { ++access_count_; }

        friend class KLruCache<Key, Value>;
};

template<typename Key, typename Value>
class KLruCache : public KICachePolicy<Key, Value> {
    public:
        using LruNodeType = LruNode<Key, Value>;
        using LruNodePtr = std::shared_ptr<LruNodeType>;
        using LruNodeMap = std::unordered_map<Key, LruNodePtr>;

        KLruCache(size_t capacity) : capacity_(capacity) {init_lru_list();}

        ~KLruCache() override = default;
        // add cache
        void put(Key key, Value value) {
            if (capacity_ <= 0) {
                return;
            }
            std::lock_guard<std::mutex> lock(lru_mutex_);
            auto it = lru_node_map_.find(key);
            if (it != lru_node_map_.end()) {
                updateExistingNode(it->second, value);
                return;
            }
            add_new_node(key, value);
        }

        /**
         * 根据键获取对应的值
         *
         * 此函数尝试在缓存中查找与给定键关联的值如果找到，它会将对应的值返回并标记该节点为最近使用
         * 如果没有找到，则返回false这个过程需要锁定缓存以保证线程安全
         *
         * @param key 用于查找的键
         * @param value 输出参数，如果找到则填充对应的值
         * @return 如果找到对应的值，返回true；否则返回false
         */
        bool get(Key key, Value& value) override {
            // 锁定互斥量以保护缓存数据结构
            std::lock_guard<std::mutex> lock(lru_mutex_);

            // 尝试在节点映射中找到对应的键
            auto it = lru_node_map_.find(key);

            // 如果找到了对应的键
            if (it != lru_node_map_.end()) {
                // 将对应的节点移动到最近使用的位置
                move_to_most_recent(it->second);

                // 获取节点的值并返回
                value = it->second->value;
                return true;
            }

            // 如果没有找到，返回false
            return false;
        }

        Value get(Key key) override {
            Value value{};
            get(key, value);
            return value;
        }

        void remove(Key key) {

        }
    private:
        void init_lru_list() {
            dummy_head_ = std::make_shared<LruNodeType>(Key(), Value());
            dummy_tail_ = std::make_shared<LruNodeType>(Key(), Value());
            dummy_head_->next_ = dummy_tail_;
            dummy_tail_->prev_ = dummy_head_;
        }
        void updateExistingNode(LruNodePtr node, const Value& value) {
            node->set_value(value);
            move_to_most_recent(node);
        }
        // add new node to node map
        void add_new_node(const Key& key, const Value& value) {
            if (lru_node_map_.size() >= capacity_) {
                evict_lru_node();
            }
            auto new_node = std::make_shared<LruNodeType>(key, value);
            lru_node_map_[key] = new_node;
        }
        // insert node in tail
        void insert_node(LruNodePtr node) {
            node->prev_ = dummy_tail_->prev_;
            node->next_ = dummy_tail_;
            dummy_tail_->prev_.lock()->next_ = node;
            dummy_tail_->prev_ = node;
        }
        // remove node from node map
        void remove_node(LruNodePtr node) {
            if(!node->prev_.expired() && node->next_) {
                auto prev = node->prev_.lock();
                prev->next_ = node->next_;
                node->next_ ->prev_ = prev;
                node->next_ = nullptr; // clear next ptr
            }
        }
        // evict lru node
        void evict_lru_node() {
            auto least_recent = dummy_head_->next_;
            remove_node(least_recent);
            lru_node_map_.erase(least_recent->Key());
        }
        // move node to
        void move_to_most_recent(LruNodePtr node) {
            remove_node(node);
            insert_node(node);
        }
    private:
        size_t capacity_; // 缓存容量
        LruNodeMap lru_node_map_; // 缓存节点map
        std::mutex lru_mutex_; // 互斥锁
        LruNodePtr dummy_head_; // 头节点
        LruNodePtr dummy_tail_; // 尾节点
};



#endif //LRU_H
